#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <string.h>
#include "gmp.h" 
using namespace std;

mpq_t* silnia(int n) {
	// Brute force, ale funkcja jest wywołana ze 20 razy z max n = 10, więc nie robi to specjalnej różnicy.
	mpq_t *silnia = (mpq_t *) malloc(sizeof(mpq_t));
	mpq_t mnoznik;
	mpq_t jeden;

	mpq_init(*silnia);
	mpq_init(mnoznik);
	mpq_init(jeden);

	mpq_set_str(*silnia, "1/1", 10);
	mpq_set_str(mnoznik, "1/1", 10);
	mpq_set_str(jeden, "1/1", 10);

	for(int i = 1 ; i < n ; i++) {
		mpq_add(mnoznik, mnoznik, jeden);
		mpq_mul(*silnia, *silnia, mnoznik);
	}

	mpq_clear(mnoznik);
	mpq_clear(jeden);

	return silnia;
}

mpq_t* serieMalejace(mpq_t* data, unsigned int n) {

	unsigned int i, j;
	unsigned int empiryzm[10];
	mpq_t *teoria = (mpq_t *) malloc(10*sizeof(mpq_t));
	mpq_t *chi = (mpq_t *) malloc(sizeof(mpq_t));
	mpq_t *obecna;
	mpq_t *nastepna;
	mpq_t jeden;
	mpq_t zliczacz;

	mpq_init(*chi);
	mpq_init(jeden);
	mpq_init(zliczacz);

	mpq_set_str(jeden, "1/1", 10);

	// Zliczamy ile razy wystapily poszczegolne dlugosci ciagow.
	for(i = 0 ; i < 10 ; ++i)
		empiryzm[i] = 0;

	j = 0;
	for(i = 0 ; i < n-1 ; ++i) {
		++j;
		obecna = &data[i];
		nastepna = &data[i+1];
		if(mpq_cmp(*obecna, *nastepna) <= 0) {
			// Koniec ciagu malejacego
			if(j > 10)
				j = 10;
			++empiryzm[j-1];
			mpq_add(zliczacz, zliczacz, jeden);
			j = 0;
			++i;
		}
	}
//	// Uwzglednienie ostatniego elementu.
//	if(i < n) {
//		++j;
//		if(j > 10)
//			j = 10;
//		++empiryzm[j-1];
//		mpq_add(zliczacz, zliczacz, jeden);
//	}

	// Obliczamy teoretyczne prawdopodobienstwa.
	for(i = 0 ; i < 10 ; ++i) {
		mpq_init(teoria[i]);
		mpq_t *sil = silnia(i+1);
		mpq_t *sil2 = silnia(i+2);
		mpq_t temp;

		mpq_init(temp);

		mpq_set_str(teoria[i], "1/1", 10);
		mpq_set_str(temp, "1/1", 10);

		mpq_div(teoria[i], teoria[i], *sil);
		mpq_div(temp, temp, *sil2);
		if(i != 9)
			mpq_sub(teoria[i], teoria[i], temp);
		
		mpq_clear(temp);
		mpq_clear(*sil);
		mpq_clear(*sil2);
	}

	// Obliczanie chi kwadrat.

	for(i=0; i < 10 ; ++i) {
		mpq_t Ys, ps;
		
		mpq_init(Ys);
		mpq_init(ps);

		mpq_set_ui(Ys, empiryzm[i], 1);
		mpq_set(ps, teoria[i]);
		
		mpq_mul(ps, ps, zliczacz);
		mpq_sub(Ys, Ys, ps);
		mpq_mul(Ys, Ys, Ys);
		mpq_div(Ys, Ys, ps);
		mpq_add(*chi, *chi, Ys);

		mpq_clear(Ys);
		mpq_clear(ps);
	}

	mpq_clear(jeden);
	mpq_clear(zliczacz);

	// Zwracamy wyniki.
	return chi;
}

mpq_t* trojwymiar(mpq_t* data, unsigned int n) {

	unsigned int i;
	unsigned int empiryzm[8];
	mpq_t *teoria = (mpq_t *) malloc(8*sizeof(mpq_t));
	mpq_t *chi = (mpq_t *) malloc(sizeof(mpq_t));
	mpq_t *trojka[3];
	mpq_t pol;
	mpq_t jednaOsma;
	mpq_t jeden;
	mpq_t zliczacz;

	mpq_init(*chi);
	mpq_init(pol);
	mpq_init(jednaOsma);
	mpq_init(jeden);
	mpq_init(zliczacz);

	mpq_set_str(pol, "1/2", 10);
	mpq_set_str(jednaOsma, "1/8", 10);
	mpq_set_str(jeden, "1/1", 10);

	// Zliczamy wystapienia empiryczne.
	for(i = 0 ; i < 8 ; ++i)
		empiryzm[i] = 0;

	for(i = 0 ; i < n-2 ; i+=3) {
		trojka[0] = &data[i];
		trojka[1] = &data[i+1];
		trojka[2] = &data[i+2];
		if(mpq_cmp(*trojka[0], pol) < 0) {
			if(mpq_cmp(*trojka[1], pol) < 0) {
				if(mpq_cmp(*trojka[2], pol) < 0)
					++empiryzm[0];
				else
					++empiryzm[1];
			}
			else {
				if(mpq_cmp(*trojka[2], pol) < 0)
					++empiryzm[2];
				else
					++empiryzm[3];
			}
		}
		else {
			if(mpq_cmp(*trojka[1], pol) < 0) {
				if(mpq_cmp(*trojka[2], pol) < 0)
					++empiryzm[4];
				else
					++empiryzm[5];
			}
			else {
				if(mpq_cmp(*trojka[2], pol) < 0)
					++empiryzm[6];
				else
					++empiryzm[7];
			}
		}
		mpq_add(zliczacz, zliczacz, jeden);
	}

	// Ustawiamy teoretyczne prawdopodobienstwa.
	for(i = 0 ; i < 8 ; ++i) {
		mpq_init(teoria[i]);
		mpq_set(teoria[i], jednaOsma);
	}

	// Obliczanie chi kwadrat.
	for(i=0; i < 8 ; ++i) {
		mpq_t Ys, ps;
		
		mpq_init(Ys);
		mpq_init(ps);

		mpq_set_ui(Ys, empiryzm[i], 1);
		mpq_set(ps, teoria[i]);
		
		mpq_mul(ps, ps, zliczacz);
		mpq_sub(Ys, Ys, ps);
		mpq_mul(Ys, Ys, Ys);
		mpq_div(Ys, Ys, ps);
		mpq_add(*chi, *chi, Ys);

		mpq_clear(Ys);
		mpq_clear(ps);
	}

	mpq_clear(pol);
	mpq_clear(jednaOsma);
	mpq_clear(jeden);
	mpq_clear(zliczacz);

	// Zwracamy wyniki.
	return chi;
}

// Potrzebne do QSORTA
int compare (const void * a, const void * b)
{
	return ( mpq_cmp(*(mpq_t*)a, *(mpq_t*)b) );
}

void WypiszWynik(mpq_t wynikBezObrobki, unsigned int d)
{
    char* out = new char[100000];
    char* tmp = new char[1];
    int added = 0;
    mpz_t dzielna, dzielnik, wynik, reszta;
    mpz_init(dzielna);
    mpz_init(dzielnik);
    mpz_init(wynik);
    mpz_init(reszta);
    
    mpq_get_num(dzielna, wynikBezObrobki);
    mpq_get_den(dzielnik, wynikBezObrobki);
    
    mpz_tdiv_qr(wynik, reszta, dzielna, dzielnik);
    
    gmp_sprintf(out, "%Zd", wynik);
    
    if ((d > 0) && (mpz_cmp_si(reszta, 0) != 0))
    {
        int len = strlen(out);
        out[len] = '.';
        len++;
        
        // fix bo jesli ulamek jest ujemny, 
        // to reszta tez bedzie ujemna co pochrzani liczenie po przecinkku
        if (mpz_cmp_si(reszta, 0) < 0)
            mpz_mul_si(reszta, reszta, -1);
        
        // dzielenie pisemne do d
        for (unsigned int i=0; i<d; i++)
        {
            mpz_set(dzielna, reszta);
            mpz_mul_si(dzielna, dzielna, 10);
            mpz_tdiv_qr(wynik, reszta, dzielna, dzielnik);
            gmp_sprintf(tmp, "%Zd", wynik);
            out[len+i] = tmp[0];
            added++;
            
            if (mpz_cmp_si(reszta, 0) == 0)
                break;
        }
        
        // czyscimy zera na koncu
        for (int i=len+added-1; i>0; i--)
        {
            if (out[i] == '0')
                out[i] = 0;
            else
            {
                out[i+1] = 0;
                break;
            }
        }
    }
    
    printf("%s\n", out);
    
    delete out;
    delete tmp;
    mpz_clear(dzielna);
    mpz_clear(dzielnik);
    mpz_clear(wynik);
    mpz_clear(reszta);
}

int main(int argc, char *argv[])
{
	if (argc != 2)
        	return 1;

	/****************** DEKLARACJA ******************/
	unsigned int i, j, n, d;
	mpq_t przedzialy[11], 
		zakresPrzedzialu, 
		Y[11], 
		jeden, 
		gmpI,
		gmpI2,
		gmpSto, 
		chi,
		gmpN,
		JprzezN,
		kPlus,
		kMinus,
		*data,
		*chiSerieMalejace,
		*chiTrojwymiar;

	/****************** INICJALIZACJA ******************/
	mpq_init(zakresPrzedzialu);
	mpq_init(jeden);
	mpq_init(gmpI);
	mpq_init(gmpI2);
	mpq_init(gmpSto);
	mpq_init(chi);
	mpq_init(gmpN);
	mpq_init(JprzezN);	
	mpq_init(kPlus);
	mpq_init(kMinus);
	
	/****************** DEFINICJA ******************/
	mpq_set_ui(jeden, 1, 1);
	mpq_set_ui(gmpSto, 100, 1);
	n=0;
	data=(mpq_t *) malloc(16777220*sizeof(mpq_t));

	/****************** WCZYTYWANIE ******************/
	if (sscanf(argv[1], "%d", &d) != 1)
	        return 1;

	while(!feof(stdin)) {
		mpq_init(data[n]);
		unsigned long res = mpq_inp_str(data[n++], NULL, 10);
		if(res == 0) {
			n--;
		}
	}
	chiSerieMalejace = serieMalejace(data, n);
	chiTrojwymiar = trojwymiar(data, n);
	qsort (data, n, sizeof(mpq_t), compare); // QSORT
	mpq_set_ui(gmpN, n, 1);
	

	/****************** OBLICZENIA ******************/
	// Wyznaczanie przedzialow
	for(i=1; i<=10; i++)
	{
		mpq_init(Y[i]);
		mpq_set_ui(zakresPrzedzialu,(i*i),100); // (i^2)/100
		mpq_init(przedzialy[i]);
		mpq_set (przedzialy[i], zakresPrzedzialu);	
	}
	
	for(i=0; i<n; i++)
	{
		// Obliczanie K+
		mpq_set_ui(JprzezN, i+1, n); // j/n
		mpq_sub(JprzezN, JprzezN, data[i]); // j/n -Fn
		if(mpq_cmp(kPlus, JprzezN) < 0) 
			mpq_set(kPlus, JprzezN); // max

		// Obliczanie K-
		mpq_set_ui(JprzezN, i, n); // j/n
		mpq_sub(JprzezN, data[i], JprzezN); // Fn - j/n
		if(mpq_cmp(kMinus, JprzezN) < 0)
			mpq_set(kMinus, JprzezN); // max

		// Wyznaczanie ile liczb zawiera sie w danych przedzialach.
		for(j=1; j<=10; j++)
			if(mpq_cmp(data[i], przedzialy[j]) < 0)
			{
				mpq_add (Y[j], Y[j], jeden);
				break;
			}
	}


	mpq_set_ui(jeden, 0, 1); // od teraz 'jeden' bedzie naszym wynikiem ostatecznym dla pojedynczej iteracji
	
	// Obliczanie chi^2. NOTE: chi w kodzie to tak na prawde chi^2
	for(j=1; j<=10; j++)
	{
		char str[2];
		sprintf(str, "%d", j);
		mpq_set_str (gmpI, str, 10);
		mpq_mul(gmpI,gmpI,gmpI); // i^2
		sprintf(str, "%d", j-1);		
		mpq_set_str (gmpI2, str, 10);
		mpq_mul(gmpI2,gmpI2,gmpI2); // (i-1)^2
		mpq_sub(gmpI, gmpI, gmpI2); //(i^2) - ((i-1)^2)
		mpq_div(gmpI,gmpI,gmpSto); //(i^2) - ((i-1)^2) / 100 = p
		mpq_mul(gmpI,gmpI,gmpN); // p*n
		mpq_sub(jeden, Y[j], gmpI); // Ys - p*n
		mpq_mul(jeden,jeden,jeden); // (Ys - p*n)^2
		mpq_div(jeden, jeden, gmpI); // (Ys - p*n)^2 / (Ys - p*n)
		mpq_add(chi,chi,jeden); // dodanie do ogolnej sumy
	}

	/****************** WYPISYWANIE ******************/	
	WypiszWynik(kPlus, d);
	WypiszWynik(kMinus, d);
	WypiszWynik(chi, d);
	WypiszWynik(*chiTrojwymiar, d);
	WypiszWynik(*chiSerieMalejace, d);


	/****************** CZYSZCZENIE ******************/
	for(i=0; i<n; i++)
		mpq_clear(data[i]);
	for(i=1; i<=10; i++)
		mpq_clear(przedzialy[i]);
	mpq_clear(zakresPrzedzialu);
	mpq_clear(jeden);
	mpq_clear(gmpI);
	mpq_clear(gmpI2);
	mpq_clear(gmpSto);
	mpq_clear(chi);
	mpq_clear(gmpN);
	mpq_clear(JprzezN);
	mpq_clear(*chiSerieMalejace);

	return 0;
}
